487. Max Consecutive Ones II
Medium

Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.

 

Example 1:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will get the maximum number of consecutive 1s. After flipping, the maximum number of consecutive 1s is 4.

Example 2:

Input: nums = [1,0,1,1,0,1]
Output: 4

 

Constraints:

  • 1 <= nums.length <= 105
  • nums[i] is either 0 or 1.

 

Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?

Accepted
59,696
Submissions
124,437
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.00 (8 votes)

Premium

Solution


Intuition

First, let's understand our problem.

"Given a binary array, find the maximum number of consecutive 1s in this array..."

Okay makes sense so far.

"...if you can flip at most one 0."

Huh? What does that even mean?

Let's translate that into something more concrete. We can rephrase "if you can flip at most one 0" into "allowing at most one 0 within an otherwise consecutive run of 1s". These statements are equal because if we had one 0 in our consecutive array, we could flip it to satisfy our condition. Note, we're not actually going to flip the 0 which will make our approach simpler.

So our new problem statement is:

"Given a binary array, find the maximum number of consecutive 1s in this array, allowing at most one 0 within an otherwise consecutive run of 1s"

Approach 1: Brute Force

Algorithm

Let's start simple and work our way up.

A brute force solution usually involves trying to check every single possibility. It'll look something like this:

  • Check every possible consecutive sequence
  • Count how many 0's are in each sequence
  • If our sequence has one or fewer 0's, check if that's the longest consecutive sequence of 1's.

Interview Tip: Often times the interviewer doesn't need to see you code the brute force solution. State the brute force approach out loud and discuss his/her expectations. Either way, communicating proactively will give you major bonus points.

Complexity Analysis

Let nn be equal to the length of the input nums array.

  • Time complexity : O(n2)O(n^2). The nested for loops turn our approach into a quadratic solution because for every index, we have to check every other index in the array.

  • Space complexity : O(1)O(1). We are using 4 variables: left, right, numZeroes, longestSequence. The number of variables are constant and do not change based on the size of the input.



Approach 2: Sliding Window

Intuition

The naive approach works but our interviewer is not convinced. Let's see how we can optimize the code we just wrote.

The brute force solution had a time complexity of O(n2)O(n^2). What was the bottleneck? Checking every single consecutive sequence. Intuitively, we know we're doing repeated work because sequences overlap. We are checking consecutive sequence blindly. We need to establish some rules on how to move our sequence forward.

  • If our sequence is valid, let's continue expanding our sequence (because our goal is to get the largest sequence possible).
  • If our sequence is invalid, let's stop expanding and contract our sequence (because an invalid sequence will never count towards our largest sequence).

The pattern that comes to mind for expanding/contracting sequences is the sliding window. Let's define valid and invalid states.

  • Valid State = one or fewer 0's in our current sequence
  • Invalid State = two 0's in our current sequence

Algorithm

Great. How do we apply all this to the sliding window?

Let's use left and right pointers to keep track of the current sequence a.k.a. our window. Let's expand our window by moving the right pointer forward until we reach a point where we have more than one 0 in our window. When we reach this invalid state, let's contract our window by moving the left pointer forward until we have a valid window again. By expanding and contracting our window from valid and invalid states, we are able to traverse the array efficiently without repeated overlapping work.

Now we can break this approach down into a few actionable steps:

While our window is in bounds of the array...

  1. Add the rightmost element to our window
  2. Check if our window is invalid. If so, contract the window until valid.
  3. Update our the longest sequence we've seen so far
  4. Continue to expand our window

This will look like this:

Current
1 / 10

Complexity Analysis

Let nn be equal to the length of the input nums array.

  • Time complexity : O(n)O(n). Since both the pointers only move forward, each of the left and right pointer traverse a maximum of n steps. Therefore, the timecomplexity is O(n)O(n).

  • Space complexity : O(1)O(1). Same as the previous approach. We don't store anything other than variables. Thus, the space we use is constant because it is not correlated to the length of the input array.

Report Article Issue

Comments: 18
horus's avatar
Read More

Simpler, one pointer: track two sets of ones, current set and previous set, resetting previous to 0 if 2 consecutive 0s are encountered. Add 1 if at least one 0 is encountered:

class Solution {

public int findMaxConsecutiveOnes(int[] nums) {
    int max = 0;
    int curr = 0, prev = 0, seenZero = 0;
    
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) {
            seenZero = 1;
            prev = curr;
            curr = 0;
        } else {
            curr++;
        }
        
        max = Math.max(max, curr + prev + seenZero);
    }
    
    return max;
}

}

23
Show 1 reply
Reply
Share
Report
antiPro's avatar
Read More

Follow up infinite stream - Maintain the 'left', 'right' and 'last seen zero'. As soon as one encounters another 0 in stream, record the maxLength; make leftIndex = zeroIndex + 1, and set zeroIndex = right = curIndex. Again continue processing the stream.

7
Reply
Share
Report
identical123's avatar
Read More

does sliding window concept work with infinite stream of input nums as well? What is the reasoning if yes/no

3
Show 2 replies
Reply
Share
Report
rcbevans's avatar
Read More

Very simple solution is to track if you have seen a zero, the count of the current run of ones, the count of the last run of ones, and the max length run you've seen.

When you see a one, increment the current run count.
When you see a zero, note that you've seen one (if you don't see one, the max consecutive ones is length of the input array), then update max total seen to be max of current max total seen and the sum of the previous run, current run, plus one to "flip" the zero between them. Then set the previous run counter to the current run counter, and reset the current run counter back to 0.

When you reach the end, if you haven't seen a zero, you can return the maximum consecutive ones to be the input length, else, it's the max of max total run seen, and the sum of previous, current, plus one, same as in the iteration.

def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        seenZero = False
        currOnes = 0
        prevOnes = 0
        
        maxRun = 0
        
        for num in nums:
            if num == 1:
                currOnes += 1
            else:
                seenZero = True
                maxRun = max(maxRun, prevOnes + 1 + currOnes)
                prevOnes = currOnes
                currOnes = 0
                
        return len(nums) if not seenZero else max(maxRun, prevOnes + 1 + currOnes)

0
Reply
Share
Report
freedomIsDivine's avatar
Read More

Why my solution below is still consuming 2ms whenever I run this piece of code, I feel like code below is exactly same as the approach here:

public int findMaxConsecutiveOnes(int[] nums) {

    int slow = 0;
    int fast = 0;
    
    int max = 0;                                 // [1,0,1,1,0]
    
    int index = 0;
    
    boolean isFlipped = false;
    
    while(fast < nums.length){
        if(nums[fast]==1){
            fast++;
        }else if(!isFlipped){
            index = fast;
            fast++;
            isFlipped = true;
        }else{
            isFlipped = false;
            slow = index+1;
            fast = slow;
        }
        
        max = Math.max(max,fast-slow);
    }
    
    return max;

}

0
Reply
Share
Report
javajunior's avatar
Read More

Very simple solution with 1 pointer.

int findMaxConsecutiveOnes(vector& nums) {

    bool skipOne = true;
    int skipIdx = 0;
    int maxLen = 0;
    int serieLen = 0;
    
    for (int i = 0; i < nums.size(); i++) {
        
        if (nums[i] == 1 || skipOne) {
            serieLen++;
            if (nums[i] == 0) {
                skipOne = false;
                skipIdx = i;
            }
            
        } else {
            
            //num == 0 and a 0 was already skipped.
            // flush the counter and readjust the current serieLen
            
            maxLen = max(maxLen, serieLen);
            
            serieLen = i - skipIdx;
            skipIdx = i;
            
        }
        
    }
    
    maxLen = max(maxLen, serieLen);
        
    return maxLen;

0
Reply
Share
Report
Agaipen's avatar
Read More

Different version using sliding window :

class Solution:
def findMaxConsecutiveOnes(self, nums ) :

    if not nums:
        return

    start = 0
    res = float('-inf')
    d = {}

    for end in range(len(nums)):

        if nums[end] == 1 :
            pass
        else :
            if 0 not in d :
                d[0] = end
            else :
                start = d.get(0) + 1
                d[0] = end

        res = max(res, end - start + 1)
    return res

0
Reply
Share
Report
pankajyogi's avatar
Read More

Little more optimized solution with two pointers than approach 2. This solution will have better runtime when numbers of zeros are less as compared to ones and are distributed. This solution is written in Java Language.
Runtime = O(n) and Space = O(1)

public int findMaxConsecutiveOnes(int[] nums) {
        int ans = 0; // it will hold the max length of valid sequence
        int start = 0; // it will hold the start index of valid sequence
        int zeroAt = -1; // store the last '0' encountered position, -1 means not encountered
        
        // iterate over numbers and noting indexes of '0' and 
        // start index of valid sequences
        for (int i = 0; i < nums.length; i++) {
            
            if (nums[i] == 0) {
                if (zeroAt > -1) { 
                    //if we have encountered a '0' already
                    // try to update the result and start position
                    ans = Math.max(ans, i - start);
                    start = zeroAt+1;
                }
                zeroAt = i; // always update new '0' position
            }
        }
        
        // finally check with last valid sequence, i.e., if nums[length-1] == 1
        ans = Math.max(ans, nums.length - start);
        
        return ans;
    }

0
Reply
Share
Report
shogunurus's avatar
Read More

Approach №2: on the second slide of algorithm visualization longestSequence should be equal to 2, not to 1, as we can swap first zero and get 2 consecutive 1s. We just need to start with longestSequence equals to 1 on the first slide.

0
Reply
Share
Report
PanosVer's avatar
Read More

Approach 1: Brute Force, when I run this approach in python3 for large lists I get 'time limit exceeded' error, but the same doesn't happen for the java solution. I am wondering if anyone has any insight as to why this is happening?

0
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
05/30/2021 20:07Accepted36 ms36 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.